public class rob2 {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int n = nums.length;
        int[] dp = new int[n];
        dp[n - 2] = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i + 1]);
        }
        int[] dp2 = new int[n - 2];
        if (n > 3) {
            dp2[n - 4] = nums[n - 2];
            for (int i = n - 5; i >= 0; i--) {
                dp2[i] = Math.max(dp2[i + 1], dp2[i + 2] + nums[i + 2]);
            }
        }
        return Math.max(dp[0], dp2[0] + nums[0]);
    }
}
